In any communications system, there is always a chance that bits will be corrupted during transmission. In wireless communication systems, this problem can be especially pronounced. To address this problem, various methods of ensuring the accurate receipt of transmitted data have been developed, such as, for example, including checksums along with the data, and/or repeating portions of, or even the entire, transmission. However, for any given communication channel, there is a maximum data rate at which information can theoretically be transmitted, known as the Shannon channel limit. Any data correction information sent thus inherently detracts from actual payload data, resulting in an actual data throughput below the Shannon limit.
In a streaming-media system such as, for example, the Sirius Satellite Digital Audio Radio System (“SDARS”), it is desirable that a client device be able to decode data and correct corrupted bits at least as quickly as the data rate of the stream. Thus, It is necessary in such systems to operate in real-time, and to be able to decode and correct data at least as quickly as it is received.
Low-Density Parity Check (“LDPC”) codes are a powerful Forward Error Correction (“FEC”) encoding technique that allows digital communication systems to achieve performance approaching the theoretical Shannon limit. While first proposed by Robert Gallagher in 1962, the hardware design complexity and costs of implementation in many potential systems of interest have often been a barrier to practical application. Recent LDPC-based FEC designs have had a number of limitations which have limited their broader application, such as, for example, (i) small code block sizes (e.g., less than a few thousand bits), which limits the achievable FEC performance; (ii) crossbar-based approaches which limits code block size, scalability, and requires custom ASIC implementations to achieve desired performance levels; and (iii) algorithm based parity check matrices restrictions based on specific code-block size restrictions and matrix structure that facilitate hardware implementation but also limit FEC performance.
LDPC codes are linear binary systematic block codes which append M parity bits to K information (data) bits to form an N-bit codeword, where N=M+K. Generally, using an LDPC encoder, the code is defined by a sparse M×N parity check matrix H, from which a generator matrix G is derived to calculate the M parity bits from the original K information bits. Then, the N-bit codeword is transmitted to the receiver through a communications channel, which introduces noise and fading. At the other side of the communications channel, the receiver synchronizes to the transmitted stream and uses an LDPC decoder to decode the received codewords and thus recovers the K informational (data) bits of interest.
An LDPC decoder is an iterative decoder that successively iterates on the received signal to recover the original, non-corrupted information bits. The fundamental decoding principle is based on an Iterative Message Passing Algorithm (“IMPA”). The processing performed by an LDPC decoder consists of two message-passing components: (i) a Parity Check-node (also known as a “Check-node”) update which updates M Check-nodes; and (ii) Bit-node update which updates N Variable (also known as a “Bit-node”) nodes. During the first half iteration, each Bit-node collects information from all associated Parity Check-nodes and creates a unique message to send back to each associated Parity Check-node. During the second half iteration, each Check-node collects information from all associated Bit-nodes and creates a unique message to send back to each associated Bit-node. The precise message calculation is determined by a decoding algorithm, which can be one of several known to those skilled in the art. The message passage calculations typically employ the Extrinsic Information Principle where each node collects messages from the other involved nodes, but excludes their own information from their update calculations.
The associated elements involved in the message computations in both update phases are defined by a sparse parity check matrix H, in which each column represents codeword bit equations, and each row represents a parity check equation. The computational complexity of each iteration is affected by code-block size, Bit-node degree (dv) (number of “1's” in a column) and Check-node degree (dc) (number of “1's” in a row), code irregularity, specific parity check code distribution, and a number of other factors.
In general, better LDPC code performance can be achieved with large code block sizes, a random H matrix, and irregular bit node degree, but these same features typically increase decoder size and complexity, and this fact has limited practically achievable systems.
What is thus needed in the art is an LDPC decoder that can overcome the aforementioned limitations. What is further needed is an LDPC decoder optimized for extended irregular repeat accumulate (“eIRA”) parity-check matrices, that can also be applicable to non-eIRA parity-check matrices in a straightforward manner.